// https://leetcode.cn/problems/group-anagrams/description/

// 算法思路总结：
// 1. 使用哈希表以排序后的字符串为键
// 2. 将原始字符串存入对应异位词分组
// 3. 遍历哈希表收集所有分组结果
// 4. 时间复杂度：O(nklogk)，空间复杂度：O(nk)

#include <iostream>
using namespace std;

#include <vector>
#include <unordered_map>
#include <algorithm>

class Solution 
{
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        vector<vector<string>> ret;
        unordered_map<string, vector<string>> up;

        for (const string& str : strs)
        {
            string sorteds = str;
            sort(sorteds.begin(), sorteds.end());
            up[sorteds].push_back(str);
        }

        for (auto& [x, y] : up)
            ret.push_back(y);
        
        return ret;
    }
};

void PrintVVS(vector<vector<string>>& vvs)
{
    for (const auto& vs : vvs)
    {
        cout << "[";
        for (const auto& s : vs)
            cout << s << " ";
        cout << "]";
    }
    cout << endl;
}

int main()
{
    vector<string> strs1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<string> strs2 = {"a"};

    Solution sol;
    auto vvs1 = sol.groupAnagrams(strs1);
    auto vvs2 = sol.groupAnagrams(strs2);

    PrintVVS(vvs1);
    PrintVVS(vvs2);

    return 0;
}